package com.study.algorithm.linkedList;
public class GetIntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 初始化两个指针，分别指向两个链表的头节点
        ListNode pA = headA;
        ListNode pB = headB;

        // 循环遍历，直到两个指针相遇
        while (pA != pB) {
            // 如果pA到达链表A的末尾，则转到链表B的头节点继续遍历
            pA = (pA == null) ? headB : pA.next;
            // 如果pB到达链表B的末尾，则转到链表A的头节点继续遍历
            pB = (pB == null) ? headA : pB.next;
        }

        // 返回相遇的节点（如果两链表不相交，此时pA和pB都为null）
        return pA;
    }

    public static void main(String[] args) {
        // 构建示例1中的链表
        // 链表A: 4->1->8->4->5
        ListNode a1 = new ListNode(4);
        ListNode a2 = new ListNode(1);
        ListNode c1 = new ListNode(8);
        ListNode c2 = new ListNode(4);
        ListNode c3 = new ListNode(5);

        a1.next = a2;
        a2.next = c1;
        c1.next = c2;
        c2.next = c3;

        // 链表B: 5->6->1->8->4->5
        ListNode b1 = new ListNode(5);
        ListNode b2 = new ListNode(6);
        ListNode b3 = new ListNode(1);

        b1.next = b2;
        b2.next = b3;
        b3.next = c1; // 连接到同一个节点8

        GetIntersectionNode solution = new GetIntersectionNode();
        ListNode result = solution.getIntersectionNode(a1, b1);

        if (result != null) {
            System.out.println("Intersected at '" + result.val + "'");
        } else {
            System.out.println("No intersection");
        }

        // 验证相交节点确实是8
        System.out.println("Intersection node should be 8: " + (result == c1));
    }
}